#include "circuitboard.h"

CircuitBoard::CircuitBoard(int n) : n(n)
{}

bool IsRightPos(const Pair<int, int> &pos, int n) {
    if (pos.first >= n || pos.second >= n) {
        return false;
    }
    if (pos.first < 0 || pos.second < 0) {
        return false;
    }
    return true;
}

void base_GetDfsPaths(const int n, Pair<int, int> pos, const Pair<int, int> &end, Path path, bool graph[10][10], Vector<Path> &res) {
    // 对应四种方向的走法
    const static int walkx[] = { -1, 0, 0, 1 };
    const static int walky[] = { 0, -1, 1, 0 };
    path.AddNode(pos);
    if (pos == end) {
        res.PushBack(path);
        return;
    }
    for (int i = 0; i < 4; i++) {
        Pair<int, int> node = MakePair(pos.first + walkx[i], pos.second + walky[i]);
        if (!IsRightPos(node, n) || graph[node.first][node.second]) {
            continue;
        }
        graph[node.first][node.second] = true;
        base_GetDfsPaths(n, node, end, path, graph, res);
        graph[node.first][node.second] = false;
    }
}

Vector<Path> CircuitBoard::GetDfsPaths(const Pair<int, int> &start, const Pair<int, int> &end) const {
    static bool graph[10][10];
    // 异常检测
    if (!IsRightPos(start, n) || !IsRightPos(end, n)) {
        return Vector<Path>();
    }
    if (start == end) {
        return Vector<Path>();
    }
    Vector<Path> res;
    memset(graph, false, sizeof(graph));
    graph[start.first][start.second] = true;
    base_GetDfsPaths(n, start, end, Path(), graph, res);
    return res;
}

Path CircuitBoard::GetBfsPath(const Pair<int, int> &start, const Pair<int, int> &end) const {
    // 对应四种方向的走法
    const static int walkx[] = { -1, 0, 0, 1 };
    const static int walky[] = { 0, -1, 1, 0 };
    static bool graph[10][10];

    // 异常检测
    if (!IsRightPos(start, n) || !IsRightPos(end, n)) {
        return Path();
    }
    if (start == end) {
        return Path();
    }
    memset(graph, false, sizeof(graph));
    Queue<Pair<Pair<int, int>, Path>> que;
    que.Push(MakePair(start, Path()));
    graph[start.first][start.second] = true;
    while (!que.IsEmpty()) {
        auto q_node = que.Front();
        que.Pop();
        q_node.second.AddNode(q_node.first);
        if (q_node.first == end) {
            return q_node.second;
        }
        for (int i = 0; i < 4; i++) {
            auto node = MakePair(q_node.first.first + walkx[i], q_node.first.second + walky[i]);
            if (!IsRightPos(node, n) || graph[node.first][node.second] == true) {
                continue;
            }
            que.Push(MakePair(node, q_node.second));
            graph[node.first][node.second] = true;
        }
    }
    return Path();
}
